package com.xucy.springboot.code;

import lombok.Data;
import org.springframework.util.CollectionUtils;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author xucy
 * @Date 2019-10-10 16:56
 * @Description 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 * 输入：1->2->4, 1->3->4
 * 输出：1->1->2->3->4->4
 **/

public class Test3 {
    /*链表*/
    @Data
    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }

    public static ListNode mergeTwoLists1(ListNode l1, ListNode l2) {

        List<Integer> integerList=new ArrayList<>();

        while (l1!=null){
            integerList.add(l1.val);
            l1=l1.next;
        }

        while (l2!=null){
            integerList.add(l2.val);
            l2=l2.next;
        }
        integerList.sort((a,b)->{
            if(a>b){
                return -1;
            }
            return 1;
        });
        ListNode listNode=new ListNode(integerList.get(0));
        for(int i=1;i<integerList.size();i++){
            ListNode curr=new Test3.ListNode(integerList.get(i));
            curr.next=listNode;
            listNode=curr;
        }


        return listNode;
    }

    public static ListNode mergeTwoLists2(ListNode l1, ListNode l2) {

        ListNode preHead=new ListNode(-1);
        ListNode pre=preHead;

        while (l1!=null && l2!=null){
            if(l1.val<=l2.val){
                pre.next=l1;
                l1=l1.next;
            }else{
                pre.next=l2;
                l2=l2.next;
            }
            pre=pre.next;
        }

        pre.next=l1==null?l2:l1;

        return preHead.next;
    }

    public static void main(String[] args) {
        ListNode l1=new Test3.ListNode(1);
        l1.next=new Test3.ListNode(2);
        l1.next.next=new Test3.ListNode(4);


        ListNode l2=new Test3.ListNode(1);
        l2.next=new Test3.ListNode(3);
        l2.next.next=new Test3.ListNode(4);

        System.out.println(mergeTwoLists2(l1, l2));
    }
}
